package com.hiwhitley.leetcode.medium;

/**
 * Created by hiwhitley on 17-2-20.
 */
public class RemoveKDigits_402 {
    public String removeKdigits(String num, int k) {
        char[] arr = new char[num.length()];
        int top = 0;
        int digit = num.length() - k;
        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);
            while (top > 0 && arr[top - 1] > c && k > 0) {
                k--;
                top--;
            }
            arr[top++] = c;
        }
        int count = 0;
        while (count < digit && arr[count] == '0') {
            count++;
        }
        return count == digit ? "0" : new String(arr, count, digit - count);
    }

    public static void main(String[] args) {
        RemoveKDigits_402 main = new RemoveKDigits_402();
        System.out.println(main.removeKdigits("144322191", 4));
    }
}
